Regent is an implicit parallel programming language with sequential semantics. Regent programs look like traditional sequential programs, and you can understand what a program is doing by reading the code top-to-bottom, just like a traditional programming language. Behind the scenes, Regent parallelizes the code, while ensuring that any parallel execution produces results identical to the original sequential execution.
For example, the two recursive calls to fib in the code below can automatically run in parallel:
In [ ]:
import "regent"
-- Define a simple recursive implementation of Fibonacci.
task fib(i : int) : int
if i <= 0 then
return 1
end
return fib(i-1) + fib(i-2) -- These calls can run in parallel.
end
task main()
regentlib.c.printf("fib(5) is %d\n", fib(5))
end
regentlib.start(main)
(To run this code, click on the box and hit Ctrl-Enter.)
Tasks, like fib above, are the fundamental unit of parallelism in Regent. Tasks are just functions: they take arguments, they have a body, and they return a result. Most task arguments, such as argument i to fib, are passed by-value, and therefore cannot be shared between tasks. Thus the task fib is trivially parallel, because it cannot interfere with other tasks.
So far, this is just standard functional programming. However, Regent can also describe imperative programs (with tasks that modify their arguments). For example, the four tasks (a, b, c, and d) below have been declared to modify their arguments.
In [ ]:
import "regent"
struct point { x : float, y : float } -- A simple struct with two fields.
-- Define 4 tasks. Ignore the task bodies for the moment; the behavior of each
-- task is soundly described by its declaration. Note that each declaration
-- says what the task will read or write.
task a(points : region(point)) where writes(points) do --[[ ... ]] end
task b(points : region(point)) where reads writes(points.x) do --[[ ... ]] end
task c(points : region(point)) where reads writes(points.y) do --[[ ... ]] end
task d(points : region(point)) where reads(points) do --[[ ... ]] end
-- Execution begins at main. Read the code top-down (like a sequential program).
task main()
-- Create a region (like an array) with room for 5 elements.
var points = region(ispace(ptr, 5), point)
new(ptr(point, points), 5) -- Allocate the elements.
-- Partition the region into 3 subregions. Each subregion is a view onto a
-- subset of the data of the parent.
var part = partition(equal, points, ispace(int1d, 3))
-- Launch subtasks a, b, c, and d.
a(points)
for i = 0, 3 do
b(part[i])
end
c(points)
for i = 0, 3 do
d(part[i])
end
end
regentlib.start(main)
Parallelism becomes more interesting in imperative programs. To preserve the sequential semantics of imperative programs, Regent executes each task in a sequential thread and discovers parallelism as it goes along. Whenever a task calls a subtask (such as a, b, c, or d above), Regent analyzes the subtask's declared side-effects (reads, writes, etc.) in combination with the actual arguments passed to determine what dependencies must be satisfied to preserve the sequential semantics of program. For example, execution of main in the program above will result in the following dependence graph.
Subtasks which are independent (i.e. are mutually unreachable in the graph) may execute in parallel and can be allowed to run asynchronously in separate threads. Unless the caller task makes an attempt to read or modify data used in a subtask, the caller will continue running asynchronously with respect to its children, so that Regent may continue to discover as much parallelism as possible.
Regent uses three factors to determine when to draw a dependence edge between two tasks: privileges, regions, and fields.
Regent tasks can mutate arguments, but only after requesting privileges on said arguments. Privileges describe how a task will interact with its arguments. (Privileges may only be declared on arguments; there are no mutable global variables in Regent.) Regent provides 3 kinds of privileges:
reads: The task will read the contents of the argument.writes: The task will write the contents of the argument.reduces<op>: The task will apply a commutative reduction operator (+, *, min, max, etc.) to the contents of the argument.Tasks which only read, or only reduce (with a common reduction operator), an argument will not interfere with each other, and can run in parallel (assuming no other arguments cause a dependence).
Privileges are checked at compile time to ensure that tasks behave in a manner consistent with the declared privileges. For example, it is an error to call a task which requires more privileges than the caller has requested. In the case below, the call to use_RW on line 6 will be reported as an error, because use_RO does not have writes privilege on r.
In [ ]:
import "regent"
task with_RW(r : region(int)) where reads writes(r) do --[[ ... ]] end
task with_RO(r : region(int)) where reads(r) do
use_RW(r) -- ERROR: with_RO doesn't have write privileges on r.
end
While privileges specify how data is used, regions answer the question of what data is being used. Conceptually, regions are containers, like arrays: they contain multiple elements, indexed by an index space (set of keys). (In the example above, the keys were opaque pointers, but they can easily be integers or multi-dimensional points as well.)
However, the analogy only goes so far. Every region is given a unique type; this ensures that regions aren't mixed up by accident or used with incorrect privileges. For example, the code below will not compile, because r and s have distinct types.
In [ ]:
import "regent"
task swap(r : region(int), s : region(int))
r, s = s, r -- ERROR: r and s are different types.
end
(Don't worry, there are other ways to swap the contents of regions, if that's what you want.)
Similarly, pointers in Regent are explicitly typed with the region they point into, so that the compiler can check that all pointer dereferences are valid:
In [ ]:
import "regent"
-- Note: The parameter x is a pointer to an int in region s.
task bad_pointer(r : region(int), s : region(int), x : ptr(int, s))
where reads writes(r) do
@x = 5 -- ERROR: bad_pointer has privileges on r, not s.
end
Regent uses a variation on region-based type systems to catch these sorts of errors. As a result, a large class of data-race and data-corruption errors are found at compile-time in Regent.
Having said that, regions are still first-class values. They can be created dynamically, and region arguments might get bound to different regions at different times during a program's execution. For example:
In [ ]:
import "regent"
task f(r : region(int)) -- Note: r will be bound to a different region on each call.
where reads(r) do
end
task main()
var s = region(ispace(ptr, 3), int)
f(s)
for i = 0, 3 do
var t = region(ispace(ptr, 5+i), int)
f(t)
end
end
regentlib.start(main)
Regions are created with the region keyword, which takes an index space and a field space (set of fields). So far, all of the field spaces have been simple types like int, but structs are frequently used in practice.
Index spaces can be built from an opaque index type like ptr, as above, or from a structured index type (in 1 or more dimensions). For example, the following code builds a 1D and a 2D region.
In [ ]:
import "regent"
struct rgba { r : int8, g : int8, b : int8, a : int8 }
task main()
var line = ispace(int1d, 5, 0) -- 5 elements starting at 0
var grid = ispace(int2d, {x = 4, y = 4}, {x = -1, y = -1}) -- 4x4 block starting at -1x-1
var vec = region(line, float)
var img = region(grid, rgba)
end
regentlib.start(main)
One last note about unstructured index spaces. When using the ptr type to build an opaque index space, the elements must be allocated individually. This is useful in building incremental data structures like lists, trees, and graphs.
In [ ]:
import "regent"
task main()
var r = region(ispace(ptr, 5), int) -- Make a region with space for 5 elements.
var x = new(ptr(int, r)) -- Allocate one element.
var y = new(ptr(int, r), 3) -- Allocate a block of 3 more.
end
regentlib.start(main)
Regions in Regent can be created with a simple type like int, or with struct types like rgba above. When using a struct type, it can be useful to declare privileges at the level of individual fields within a region. For example, in the example below, filter_r and filter_gb can run in parallel.
In [ ]:
import "regent"
struct rgba { r : int8, g : int8, b : int8, a : int8 }
task filter_r(grid : ispace(int2d), img : region(grid, rgba))
where reads writes(img.r) do
-- ...
end
task filter_gb(grid : ispace(int2d), img : region(grid, rgba))
where reads writes(img.{g, b}) do
-- ...
end
task main()
var grid = ispace(int2d, {x = 4, y = 4})
var img = region(grid, rgba)
filter_r(grid, img) -- These two tasks can run in parallel.
filter_gb(grid, img)
end
regentlib.start(main)
Fields are frequently a source of unexpected task parallelism, which would otherwise be difficult to capture. In large applications, this additional parallelism can be especially helpful because it allows Regent to schedule tasks around high-latency operations such as network communication.
With privileges, regions, and fields, we are already able to exploit task parallelism in Regent. Two tasks that use a region read-only (or with reductions) will be able to run in parallel, as will tasks that use different regions read-write.
Partitions allow Regent to take advantage of data parallelism. Partitions subdivide a region into multiple pieces, so that multiple tasks can run on those pieces in parallel.
Partitions are not copies of the data, but views. Changes to a subregion inside a partition will be automatically reflected in the parent. This means, for example, that multiple partitions can be used to slice the region's data different ways, and that data will get shuffled between tasks automatically when accessing the different partitions.
There are several ways to create partitions. One simple but limiting way to create a partition is to divide the parent into roughly equal parts, using partition(equal, ...) as we saw above. An alternative which provides significantly more user control is to assign each element in a region to a color (i.e. in a field of each element), and then pass that coloring to the partition operator. This approach can be used with programs like METIS to provide high quality partitions of various data structures with minimal hassle. Yet other ways to create partitions are covered in the Regent language reference.
In [ ]:
import "regent"
struct elt { value : int, c0 : int, c1 : int }
-- This task increments each element in a region by the number of elements.
task inc_by_size(r : region(elt))
where reads writes(r) do
var size = 0
for x in r do
size += 1
end
for x in r do
x.value += size
end
end
task main()
-- Make a region and allocate 4 elements.
var r = region(ispace(ptr, 4), elt)
var x0 = new(ptr(elt, r))
var x1 = new(ptr(elt, r))
var x2 = new(ptr(elt, r))
var x3 = new(ptr(elt, r))
fill(r.value, 0) -- Clear the value field.
-- Make two different colorings of the region in c0 and c1.
x0.c0, x1.c0, x2.c0, x3.c0 = 0, 0, 1, 2
x0.c1, x1.c1, x2.c1, x3.c1 = 0, 1, 1, 1
-- Make the two partitions from c0 and c1.
var colors = ispace(int1d, 3) -- Note: Each partition will have 3 subregions.
var part0 = partition(r.c0, colors)
var part1 = partition(r.c1, colors)
-- Call inc_by_size on each partition.
for color in colors do
inc_by_size(part0[color])
end
for color in colors do
inc_by_size(part1[color])
end
for x in r do
regentlib.c.printf("element %d has value %d\n", int(x), x.value)
end
end
regentlib.start(main)
With this we're running in parallel! Each partition is individually disjoint (subregions do not overlap), so each for loop (lines 37-39 and 40-42) can run in parallel. Between (and around) the loops, Regent will handle any data shuffling necessary to ensure that all views onto the data remain consistent.
We hope you've enjoyed this introduction to Regent! Feel free to stay here and play around with the code as long as you like.
If you'd like to see how to build a larger Regent application, try our tutorial on building a circuit simulation in Regent.
Alternatively, if you just want to get started, go ahead and install Regent on your own machine.
You might also enjoy reading the source, language reference, or paper. There is also an older paper which describes a fragment of the type system.
Regent is an active research project at Stanford University. More details about the team are available at the Legion homepage.